4.4 红黑树

红黑树是一种自平衡的二叉搜索树，它通过特定的颜色属性和旋转操作来确保树的平衡性，从而保证查找、插入和删除操作的效率达到O(log n)。

红黑树与AVL 树一样，都是为了保持二叉搜索树的平衡，但红黑树允许一定程度的不平衡，通过特定的颜色规则来维持整体的近似平衡，而不是像AVL 树那样严格要求左右子树的高度差不超过1。

本节代码存放目录为 lesson9

概念及原理

红黑树是一种自平衡的二叉搜索树，它的每个节点都有一个颜色属性，红色或者黑色，所以我们叫它红黑树。

红黑树具备以下特点：

节点要么是红色的，要么是黑色的。
根节点永远是黑色的。
所有叶子节点都是黑色的。注：叶子节点指的是树的末端指向空节点的指针，在红黑树中这些末端的空节点被视为黑色叶节点。

比如我们有这样的红黑树：
```
          10B
         /   \
       5R     15B
```
这颗红黑树实际应该别视为这样：
```
          10B
         /   \
       5R     15B
      / \     /  \
   NILB NILB NILB NILB
```
也就是说，在5、15节点的末尾我们又新增了nil左右节点，这些节点都是黑色的。
如果一个节点是红色的，那么它的两个子节点必须是黑色的，也就是说红色节点不能连续相连。
从任意节点到其每个叶子节点的所有路径上，必须具有相同数量的黑色节点。这一点保证了树的平衡性，同时这也是为什么上文我们会在最后新增nil节点的原因，

这些性质确保了红黑树不会在插入或删除节点后失去平衡，并且可以保证最坏情况下查找、插入和删除的时间复杂度都是 O(log n)。

红黑树的旋转与变色

在红黑树中，当插入或删除节点时，可能会违反上述性质中的一项或多项，因此需要通过旋转和变色来修复树。

这一点与AVL 树是一样的，当插入或删除元素时需要重新进行平衡性检查，形成新的平衡树。

左旋和右旋：这些旋转与AVL 树中的旋转操作类似，通过旋转调整子树的结构。
颜色反转（变色）：为了恢复红黑树的平衡性，可能需要改变某些节点的颜色。

如下图所示展示了一个平衡的红黑树：

        10B
       /   \
     5R     15B
    / \     /  \
   3B  7B  13R  20B

根节点 10 是黑色的，符合红黑树性质。
所有红色节点的子节点都是黑色，满足红黑树的规则（5 和 13 是红色，且它们的子节点都是黑色，其中13的子节点为nil B）。
从根节点到每个叶节点的路径上，黑色节点的数量相同（每条路径上有两个黑色节点）。

红黑树的插入操作

红黑树的插入操作类似于二叉搜索树，但插入后可能会破坏红黑树的平衡。因此需要通过调整颜色和旋转来恢复平衡。

插入步骤如下所示：

按照二叉搜索树的规则插入节点，初始插入的节点颜色为红色。
从插入节点向上回溯，检查是否违反了红黑树的性质：
- 如果父节点是黑色的，树保持平衡，不需要任何调整。
- 如果父节点是红色的（这会违反红黑树的规则），则需要进行旋转和颜色变换来恢复平衡。

如下示意图所示：

1. 插入 10：

   - 初始插入 10 作为根节点，颜色为黑色。

        10B

2. 插入 5：

   - 插入 5 作为 10 的左子节点，初始为红色。

        10B
       /
     5R

3. 插入 15：

   - 插入 15 作为 10 的右子节点，初始为红色。

        10B
       /   \
     5R     15R

4. 插入 3：

   - 插入 3 作为 5 的左子节点，初始为红色。

   - 5R 和 3R 连续红色，违反红黑树性质，需要调整。

   - 调整：将 5 变为黑色，此时违反黑色节点数量一样的原则，将 15R 变为 15B。

        10B
       /   \
     5B     15B
    /
   3R

5. 插入 7：

   - 插入 7 作为 5 的右子节点，初始为红色。

        10B
       /   \
     5B     15B
    / \
   3R  7R

6. 插入 12：

   - 插入 12 作为 15 的左子节点，初始为红色。

        10B
       /   \
     5B     15B
    / \    /
   3R  7R 12R

7. 插入 17：

   - 插入 17 作为 15 的右子节点，初始为红色。

        10B
       /   \
     5B     15B
    / \    /  \
   3R  7R 12R 17R

总的来说，我们的流程大致是这样的：先插入的时候为红色，如果插入后不符合红黑树规范，那么调整当前插入的颜色以及其他节点的颜色。

红黑树的删除操作

红黑树的删除操作与二叉搜索树的删除操作类似，但删除后同样可能破坏红黑树的平衡，需要通过颜色调整和旋转来恢复平衡。

删除步骤如下所示：

找到要删除的节点，并按二叉搜索树的规则进行删除。
处理删除后的不平衡情况：
- 如果删除的节点或其替代节点是红色，则只需要简单地删除或调整颜色。
- 如果删除的节点或其替代节点是黑色，则可能会违反红黑树的性质，需要通过旋转和颜色调整来恢复平衡。

如下示意图所示：

当前红黑树如下：
         10B
       /   \
     5B     15B
    / \    /  \
   3R  7R 12R 17R

1. 删除 17：

   - 不影响红黑树的平衡结构，直接删除即可

        10B
       /   \
     5B     15B
    / \    /  
   3R  7R 12R

2. 删除 15：

   - 删除 15 后，12 移动到 15 节点

        10B
       /   \
     5B     12R
    / \    
   3R  7R

   - 直接替换后，不满足：黑色数量相等的规范

   - 调整：将 12R 调整为 12B

           10B
       /   \
     5B     12B
    / \    
   3R  7R

在删除时，我们除了需要检查树高度平衡外，我们还需要针对颜色标记进行进一步的检查，如果不满足就调整树结构。

红黑树的旋转操作

红黑树中的旋转操作与AVL 树中的旋转类似。主要有以下两种：

左旋：围绕一个节点进行左旋，把该节点的右子节点提升为新的根节点。
右旋：围绕一个节点进行右旋，把该节点的左子节点提升为新的根节点。

左旋示例：

右旋示例：

这一点与AVL 树是类似的，同时左右旋、右左旋也是同样具备的，也就是说红黑树在这些基础上还增加了颜色标记处理。

红黑树在现实中的应用

Linux内核中的进程调度：红黑树被广泛应用于 Linux 内核中，用于维护定时器和调度任务。
Java的TreeMap和TreeSet：Java 集合框架中的 TreeMap 和 TreeSet 都使用红黑树来保证键的有序性，并提供 O(log n) 的查找、插入和删除操作。
C++的map和set：C++ 标准库中的 map 和 set 底层也基于红黑树实现。
数据库系统：红黑树在数据库系统中用于实现内存中的平衡二叉树索引结构。

Go语言的实现

实现代码如下所示：

const (
    RED   = true
    BLACK = false
)

// 定义红黑树节点结构
type RBTree struct {
    data   int
    left   *RBTree
    right  *RBTree
    color  bool // true表示红色，false表示黑色
}

// 旋转操作

// 左旋
func leftRotate(t *RBTree) *RBTree {
    newRoot := t.right
    t.right = newRoot.left
    newRoot.left = t
    newRoot.color = t.color
    t.color = RED
    return newRoot
}

// 右旋
func rightRotate(t *RBTree) *RBTree {
    newRoot := t.left
    t.left = newRoot.right
    newRoot.right = t
    newRoot.color = t.color
    t.color = RED
    return newRoot
}

// 颜色翻转
func flipColors(t *RBTree) {
    t.color = RED
    t.left.color = BLACK
    t.right.color = BLACK
}

// 插入节点
func (t *RBTree) insert(data int) *RBTree {
    if t == nil {
        return &RBTree{data: data, color: RED}
    }

    if data < t.data {
        t.left = t.left.insert(data)
    } else if data > t.data {
        t.right = t.right.insert(data)
    }

    // 修复红黑树性质
    if isRed(t.right) && !isRed(t.left) {
        t = leftRotate(t)
    }
    if isRed(t.left) && isRed(t.left.left) {
        t = rightRotate(t)
    }
    if isRed(t.left) && isRed(t.right) {
        flipColors(t)
    }

    return t
}

// 判断节点是否是红色
func isRed(t *RBTree) bool {
    if t == nil {
        return false
    }
    return t.color == RED
}

// 中序遍历
func (t *RBTree) inOrder() {
    if t == nil {
        return
    }
    t.left.inOrder()
    fmt.Printf("%d ", t.data)
    t.right.inOrder()
}

func main() {
    root := &RBTree{data: 10, color: BLACK}
    root = root.insert(20)
    root = root.insert(30)
    root = root.insert(40)
    root = root.insert(50)
    root = root.insert(25)

    fmt.Println("中序遍历结果：")
    root.inOrder()  // 输出：10 20 25 30 40 50
}

执行结果输出如下所示：

中序遍历结果：
10 20 25 30 40 50

小结

红黑树也是一种自平衡的二叉搜索树，它在AVL 树的基础上增加了颜色识别，通过颜色规则的控制进一步保证二叉树的平衡。

红黑树在实际应用中也比较广泛，在学习完本节后可能还是有一些不明白，红黑树到底是怎么使用Go实现的。

有这种想法是正常的，数据结构本身就是一种比较抽象的东西，我们可以通过一些实际的案例及算法去训练，这样结合起来之后就会对于二叉树有一个全面的了解。

4.4 红黑树

4.4 红黑树

概念及原理

红黑树的旋转与变色

红黑树的插入操作

红黑树的删除操作

红黑树的旋转操作

红黑树在现实中的应用

Go语言的实现

小结

results matching ""

No results matching ""